Mi manual de algoritmos/version_world_finals_2009/src/grafos/floyd.cpp

   1 //Complejidad: O(V^3)
   2 //No funciona si hay ciclos de peso negativo
   3 // g[i][j] = Distancia entre el nodo i y el j.
   4 unsigned long long g[MAXNODES][MAXNODES];
   5 void floyd(int n){
   6   //Llenar g antes
   7   for (int k=0; k<n; ++k){
   8     for (int i=0; i<n; ++i){
   9       for (int j=0; j<n; ++j){
  10         g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  11       }
  12     }
  13   }
  14   //Acá se cumple que g[i][j] = Longitud de la ruta más corta
  15   //de i a j.
  16 }